package com.zyk.leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangsan
 * @date 2021/5/7 9:58
 */
public class C382 {


    // 给一个单链表, 随即返回一个节点, 且保证每个节点返回的次数基本相等
    static class Solution {

        ListNode head;

        public Solution(ListNode head) {
            this.head = head;
        }

        public int getRandom() {
            ListNode cur = head.next; //, res = head;
            int res = head.val, count = 1;
            while (cur != null) {
                count++;
                if ((Math.random() * count + 1) < 2) {   // 每个球 都有 1/它包括他之前 的概率替换掉答案
                    res = cur.val;
                }
                cur = cur.next;
            }
            return res;
        }
    }
    static class Right {

        List<ListNode> lists = new LinkedList<>();
        int size;

        public Right(ListNode head) {
            ListNode cur = head;
            while (cur != null) {
                size++;
                lists.add(cur);
                cur = cur.next;
            }
        }

        public int getRandom() {
            return lists.get((int) (Math.random() * size)).val;
        }
    }


    // for test
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);

        int times = 100000;

        Solution solution = new Solution(head);
        int[] count = new int[7];
        for (int i = 0; i < times; i++) {
            count[solution.getRandom()]++;
        }
        System.out.println(Arrays.toString(count));
        Right right = new Right(head);
        int[] count2 = new int[7];
        for (int i = 0; i < times; i++) {
            count2[right.getRandom()]++;
        }
        System.out.println(Arrays.toString(count2));
    }


}
